package oj;

public class LC143 {
    //找到链表中点+反转+合并
    public void reorderList(ListNode head) {
        if(head==null) return;
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode newHead=slow.next;
        slow.next=null;
        ListNode nHead=reverse(newHead);
        ListNode node1=head;
        ListNode node2=nHead;
        while(node1!=null && node2!=null){
            node1=node1.next;
            node2=node2.next;

            head.next=nHead;
            head=node1;

            nHead.next=head;
            nHead=node2;
        }
    }
    private ListNode reverse(ListNode head){
        if(head==null || head.next==null) return head;
        ListNode sec=head.next;
        ListNode newH=reverse(sec);
        sec.next=head;
        head.next=null;
        return newH;
    }

    //利用数组存储链表
//    public void reorderList(ListNode head) {
//        if(head==null) return;
//        List<ListNode> list=new ArrayList<>();
//        for(ListNode x=head;x!=null;x=x.next){
//            list.add(x);
//        }
//        int low=0;
//        int high=list.size()-1;
//        while(low<high){
//            list.get(low).next=list.get(high);
//            low++;
//            if(low==high) break;
//            list.get(high).next=list.get(low);
//            high--;
//        }
//        list.get(low).next=null;
//    }
}
